package JZ_Offer.algorithm.search;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
 *
 * @Author piper
 * @Date 2019/12/25 10:07 上午
 */
public class JZ38_字符串的排列 {

    private static StringBuilder sb = null;

    /**
     * 每次从原来字符中选择一位拿出来，然后原来字符串减去这个字符，当拿出来三次后，就得到一个新的排列
     */
    private static ArrayList<String> PermutationHelp1(String str) {
        if (str == null || "".equals(str)) {
            return new ArrayList<>();
        }
        TreeSet<String> set = new TreeSet<>();
        sb = new StringBuilder(str);
        itr(sb, new StringBuilder(), set);
        return new ArrayList<>(set);
    }

    private static void itr(StringBuilder a, StringBuilder b, TreeSet<String> set) {
        if (b.length() == sb.length()) {
            set.add(b.toString());
            return;
        }

        for (int i = 0; i < a.length(); i++) {
            StringBuilder aa = new StringBuilder(a);
            char c1 = aa.charAt(i);
            itr(aa.deleteCharAt(i), new StringBuilder(b).append(c1), set);
        }
    }

    /**
     * 每次交换字符就是一种新的排序
     */
    private static void PermutationHelp(int pos, String str, TreeSet<String> set) {
        if (pos + 1 == str.length()) {
            set.add(str);
        }

        for (int i = pos; i < str.length(); i++) {
            String newstr = swap(pos, i, str.toCharArray());
            PermutationHelp(pos + 1, newstr, set);
//            不需要进行回溯了，因为新建了newstr进行递归，并没有使用旧值str
//            swap(pos, i, str.toCharArray());
        }
    }

    private static String swap(int pos, int i, char[] str) {
        char temp = str[pos];
        str[pos] = str[i];
        str[i] = temp;
        return new String(str);
    }

    public static void main(String[] args) {
        System.out.println(PermutationHelp1("aab").toString());
        TreeSet<String> set = new TreeSet<>();
        PermutationHelp(0, "aab", set);
        System.out.println(set.toString());
    }

}
